from typing import List
import functools

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        # 自底向上
        # dp[i] 表示金额为i需要最少的硬币
        # dp[i] = min(dp[i], dp[i - coins[j]]) j所有硬币
        dp = [float("inf")] * (amount + 1)
        dp[0]= 0
        for i in range(1, amount+ 1):
            s = []
            for c in coins:
                if i -c >=0:
                    s.append(dp[i-c])
                else:
                    s.append(float("inf"))
            # print("s=", s)
            dp[i] = min(s) + 1
            # dp[i] = min(dp[i - c] if i - c >= 0 else float("inf") for c in coins ) + 1

        return dp[-1]

if __name__ == "__main__":
    coins = [1, 2, 5]
    amount = 11
    res = Solution().coinChange(coins, amount)
    print(res)